Perron-Frobenius理论

发表于 |

1907年O.Perron发现正矩阵的谱有特别有趣的性质。G.Frobenius在1908-1912年间将Perron的工作推广到不可约非负矩阵的情形，并得到了新的进一步结果。Ferron-Frobenius理论有很多证明方式，下面介绍H.Wielandt的优美证明。

两个矩阵X和Y称为置换相似的，若存在一个置换矩阵P满足$P^TXP=Y$。设$A\in M_n$.称A为可约的，若A置换相似于一个形如
$$\left( \begin{matrix} B & 0\\ C & D \end{matrix} \right)$$
其中B，D为方阵，若A不是可约的，则称A是不可约的。

引理1 设A是n(n>1)阶不可约非负矩阵，$y\in \mathbf{R}_+^{n} \backslash \lbrace 0 \rbrace $ 且至少有一个分量为0.则 $(I+A)y$ 的正分量的个数大于y的正分量个数。

Proof： 设y恰好有k个正分量，$1 \leq k \leq n-1$。设P是置换矩阵使得$x=Py$的前k个分量为正，其它为0，因为A是非负矩阵，所以$(I+A)y$的零分量个数不会超过$n-k$。假设这个个数等于$n-k$，则有$y_i = 0 \Rightarrow (Ay)_i = 0$。即$(Py)_i = 0 \Rightarrow (PAy)_i = 0$ 于是$(PAP^Tx)_i = 0,i=k+1,\cdots,n$，设$B=PAP^T$. 则当$k+1 \leq i \leq n$ 时，
$$(Bx)_i = \sum _{j=1} ^{n} b _{ij} x _j = \sum _{j=1} ^{k} b _{ij} x _j = 0$$

但当$1 \leq j \leq k$时，$x _ j >0$。所以$b _{ij}=0,k+1 \leq i \leq n,1 \leq j \leq k$ 矛盾于A不可约,证毕。

由引理1，我们马上得到以下结论

引理2 设A是n阶不可约非负矩阵，$y\in \mathbf{R}_+^{n} \backslash \lbrace 0 \rbrace $ 则 $(I+A)^{n-1}y>0$.
引理3 设$n>1$则n阶非负矩阵A不可约当且仅当，$y\in \mathbf{R}_+^{n} \backslash \lbrace 0 \rbrace $ 则 $(I+A)^{n-1}>0$.

proof: 应用引理2，考虑$(I+A)^{n-1}e_j$即可。

引理4 一个不可约非负矩阵的非负特征向量是正特征向量。

Proof：设A是不可约非负矩阵，$Ax=\lambda x, x \geq 0,x \neq 0$。显然 $\lambda \geq 0$ 我们有
$$(I+A)x = (1 + \lambda)x$$
因此$(1+A)x$与$x$有相同个数的正分量，有引理1知$x>0$。

Collatz-Wielandt函数

设A是一个n阶非负矩阵。A的Collatz－Wielandt函数$f_A \colon \mathbf{R} _+ ^n \backslash \lbrace 0 \rbrace \to \mathbf{R} _+$
定义为
$$f_A(x) = \min _{ x _i \neq 0 } \frac{(Ax) _i }{x _i}$$

引理5 设A为n阶非负不可约矩阵，则
  1. $f_A(tx) = f_A(x), \forall t > 0 $
  2. $f_A(x) = \max \lbrace \rho | Ax-\rho x \geq 0 \rbrace$
  3. 设 $x \in \mathbf{R} _+ ^n \backslash \lbrace 0 \rbrace $ ,记 $y = (I+A)^{n-1} x$ ,则 $ f_A(y) \geq f_A(x)$。

Proof：(1),(2)显然。下证明(3)
我们有$Ax- f_A(x)x \geq 0$，在等式两边左乘以$(I+A)^{n-1}$并利用$A$和$(I+A)^{n-1}$乘法可交换的性质，得到
$$A(I+A)^{n-1}x - f_A(x)(I+A)^{n-1}x \geq 0$$
即
$$Ay - f_A(x)y \geq 0$$
再由(2)就得到(3)。

容易证明：$f_A$是有界函数，实际上，$f_A$非负且不超过$A$的最大行和。
记$\Omega _n = \lbrace x \in \mathbf{R} _+ ^n | \sum _{i=1} ^n = 1 \rbrace$引理5.1说明，我们只需要在$ \Omega _n$上研究$f_A$即可。显然$\Omega _n$是一个紧集，但是$f_A$可能在$\Omega _n$ 的边界不连续。但是我们仍然有引理6。

引理6 设A是n阶非负不可约矩阵，则$f _ A$在$\mathbf{R} _+ ^n \backslash \lbrace 0 \rbrace $上可以取到最大值。

Proof： 记
$$\Delta = (I+A)^{n-1} \Omega _n = \lbrace y | y=(I+A)^{n-1} x ,x \in \Omega _n \rbrace$$
则$\Delta$是一个紧集，且有引理2知$\Delta$中向量都是正向量，因此$f _ A$ 在$ \Delta $上连续，由Weierstrass定理，$f_A$在某一点$y^0 \in \Delta$取得$f _ A$在$\Delta$上的最大值。记 $z ^0 = y ^0 / \sum_{i=1} ^n y _i ^0 \in \Omega _ n$。$\forall x \in \Omega _n$，记 $ y=(I+A)^{n-1}x $利用引理5可知
$$f_A(x) \leq f_A(y) \leq f_A(y ^0) = f_A(z^0)$$
这就证明了$f_A$ 在 $z^0$上取到它在$\Omega _n$上的最大值。利用对$\forall z \in R _+ ^n \backslash \lbrace 0 \rbrace$和引理6.1有
$$f_A(z) \leq f_A(\frac{z}{\sum_{i=1}^n z _i}) = f_A(z^0)$$
可见$f_A$在$z^0$处取到它在$R _+ ^n \backslash \lbrace 0 \rbrace$上的最大值。

矩阵A的谱半径$\rho(A)$定义成矩阵A的所有特征值的绝对值的最大值。
万事俱备了，下面开始介绍著名的Perron-Frobenius定理

定理7(Perron-Frobenius) 设A是n(n>1)阶非负不可约矩阵，则下面结论成立。
  1. $\rho(A)>0$ 且 $\rho(A)$是矩阵A的一个单特征值。
  2. A有一个对应于$\rho(A)$的正特征向量。
  3. A的每个非负特征向量都对应于特征值$\rho(A)$.

Proof：由引理6存在$x^0 \in R _+ ^n \backslash \lbrace 0 \rbrace $满足
$$f_A(x^0) \geq f_A(x), \forall x \in \mathbf{R} _+ ^n \backslash \lbrace 0 \rbrace$$

记$r=f_A(x^0)$。取$u=(1,\cdots,1)^T$。因为$A$不可约，没有零行，所以
$$r \geq f_A(u) = \min \sum _ {i=1} ^n a _{ij} > 0$$
下面证明r是A的一个特征值，我们有
$$Ax^0 - rx^0 \geq 0$$
假设$Ax^0 - rx^0 \neq 0$。由引理5.2
$$(I+A)^{n-1} (Ax^0 - rx^0) > 0$$
即
$$Ay^0 - ry^0> 0$$
其中$y_0 = (I+A)^{n-1}x^0 >0$。因此存在一个正数 $\epsilon$ 使得
$$Ay^0 - (r+\epsilon)y^0> 0$$
由引理5.2，$f_A(y^0) \geq r+\epsilon > r$这就与$r=f_A(x^0)$的最大性矛盾。所以$Ax^0=rx^0$。从而r是A的一个特征值，$x^0$是A的一个特征向量。有引理4知，$x^0$是正向量。
设$\lambda$是A的任何一个特征向量：$Ax=\lambda x$ 则
$$|\lambda||x| \leq A|x|$$
于是$|\lambda| \leq f _ A(|x|) \leq r$ 这表明$r = \rho(A)$。

现证明$\rho(A)$是单特征值，我们先证明$\rho(A)$的几何重数是1，设
$$Ay = \rho(A) y, 0 \neq y \in \mathbf{C} ^n$$
则
$$A|y| \geq \rho(A)|y|$$
上面证明过程表面上式是等式。且$|y|>0$。可见，A的对应于$\rho(A)$的特征向量不含零分量。设y和z是对应$\rho(A)$的特征向量。则$|y|>0,|z|>0.z_ 1 y-y_ 1 z$属于$\rho(A)$的特征子空间，但$z_ 1 y-y_ 1 z$的第一个分量为0，所以它不可能是$\rho(A)$的特征值，因此，$z_ 1 y-y_ 1 z＝0$，y和z线性相关，所以$\rho(A)$的几何重数为1.
为了证明$r=\rho(A)$是特征多项式$\phi(\lambda) = det(\lambda I - A)$的单根，只需证明，导数$\phi'(r) \neq 0$。用$adj(Z)$表示Z的伴随矩阵。我们有
$$\phi'(\lambda) = \sum_{i=1}^n det[(\lambda I - A)(i|i)] =tr[adj(\lambda I - A)]$$
记$B(r)=adj(rI-A)$则$\phi’(r) = tr B(r)$,
$$(rI-A)B(r) = det(rI-A)I =0$$
因为r的几何重数为1，所以$rank(rI-A)=n-1$，于是$B(r) \neq 0$。设b是$B(r)$的任意一个非零列，则$(rI-A)b=0$,因此b是A的对应于r的特征向量，但是A有一个对应于r的特征向量$x^0$，且因为r的几何重数为1，因此b是$x^0$的一个常数倍，从而$b>0$或者$b<0$。这就证明了$b(r)$的每一列要么是零列，要么是正向量，要么是负向量。考虑$[B(r)]^T = adj(rI-A^T),r=\rho(A)=\rho(A^T)$ 。上面结论应用于$[B(r)]^T$的列，所以$B(r)>0$或者$B(r)<0$,从而$\phi’(r)=tr[B(r)] \neq 0$,这就证明了$\rho(A)$是单特征值。
我们已经证明了(1),(2)。现在来证明(3)。设$y>0$是$A^T$对应于$\rho(A)$的特征向量，设x是A的任意一个非负特征向量：$Ax = \mu x$。则
$$\mu y^T x = y^T Ax = \rho(A)y^Tx$$
因为$y^Tx>0$,我们有$ \mu = \rho(A) $，证毕。
注：由引理4，A的非负特征向量实际上都是正向量，因此结论3可叙述成：在A的所有特征向量中，只有$\rho(A)$有非负特征向量。上述证明还确定了以下结果：

定理8. 设A是一个n(n>1)阶不可约非负矩阵，则
$$\rho(A) = \max \lbrace f_A(x)|x\in \mathbf{R} _+ ^n \backslash \lbrace 0 \rbrace \rbrace$$

若$\mathbf{R} _+ ^n \backslash \lbrace 0 \rbrace ,f_A(x) = \rho(A)$则$\rho>0$且x是对应于$\rho(A)$的一个特征向量。

定理9. 设A是一个非负矩阵，则$\rho(A)$是A的特征值，且A有一个对应于$\rho(A)$的非负特征向量。

Proof：设A的阶数为n，定理对$n=1$是平凡地成立。下面设$n=2$，用J表示元素全为1的矩阵。
对于正整数k，记$A_k = A + \frac{1}{k} J$是一个正矩阵，由Perron-Frobenius定理，$A_k$在$\Omega _n = \lbrace x \in \mathbf{R} _+ ^n | \sum _{i=1} ^n = 1 \rbrace$中有唯一一个对应于$\rho(A_k)$的特征向量$x^k$
因为向量序列$\lbrace x^k \rbrace $有界因此，由Bolzano-Weierstrass定理,$\lbrace x^k \rbrace $有收敛子列$\lbrace x^{k_i} \rbrace: \lim _{i \to \infty } = x$。显然$x \in \Omega _n$因此$$A _{k_i}x^{k _i} = \rho(A _{k _i}) x^{k _i}$$
注意到$A _{k_i} \to A , \rho(A _{k _i}) \to \rho(A)$ 因此$i \to \infty$得到$Ax = \rho(A)x$，证毕。

至此，Prron-Frobenius定理介绍完毕。下面介绍一个非负矩阵特征值的界。
定理10 设A是一个n阶矩阵非负矩阵，则
$$\min_{1 \leq i \leq n} r_i \leq \rho(A) \leq \max_{1 \leq i \leq n} r_i$$
$$\min_{1 \leq i \leq n} c_i \leq \rho(A) \leq \max_{1 \leq i \leq n} c_i$$
其中$r_i, c_j$分别为A的第i行和和第j列和。
Proof：设x是$A^T$的一个Perron向量(对应于谱半径的非负特征向量)。因为$\rho(A^T)=\rho(A)$从$A^Tx=\rho(A)x$得
$$\rho(A)x_i = \sum_{k=1}^n a_{ki}x_k \qquad i = 1,\cdots,n.$$
将这些等式相加得到$\rho(A) \sum_{i=1}^n x_i =\sum_{k=1}^n r_k x_k$，即
$$\rho(A)= \frac{\sum_{k=1}^n r_k x_k }{\sum_{i=1}^n x_i}$$
证毕。

定理11(Wielandt) 设A是n(n>1)阶不可约非负矩阵，且$|B| \leq A$ 则对于B的任何特征值$\lambda$有
$$|\lambda| \leq \rho(A)$$

Proof：设$Bx=\lambda x$则$|B||x| \geq |\lambda||x|$,但是$|B| \leq A$，所以$|\lambda| |x| \leq |B||x| \leq A |x|$，由引理5.2和8知
$$|\lambda| \leq f_A(|x|) \leq \rho(A)$$
证毕。

根据谱半径的连续性，我们马上有如下推论

  1. 若矩阵A非负，且$|B| \leq A$,则$\rho(B) \leq \rho(A)$
  2. 对任意矩阵A，$\rho(A) \leq \rho(|A|)$.(这个直接证明也可以)

本文源自詹兴致所著的《矩阵论》第六章。

定理虽然很长但是整个过程十分优美，思路十分清晰，仔细分析每一步还是很容易看懂的，并且在证明的过程中就能体会为什么一开始要提出“非负不可约矩阵”的概念了，然后应用连续性把一些结果推广到非负矩阵。